from Room import Room
from Person import Person, Professions

#Function for finding an element in a list
#Example: Find(List, lambda x : x.name = "Kalle")
def Find(list, func) :
    for item in list :
        if func(item) :
            return item
    return None

class ConstraintSatisfaction : 
    Rooms = []
    Persons = []
    RoomFittingTests = 0

    def __init__(self) :
        self.Rooms = []
        self.Persons = []
        self.RoomFittingTests = 0

    #Adds all rooms with Ids in the near list to the specified rooms list of Near rooms
    def SetRoomNear(self, room, near) :
        r = Find(self.Rooms, lambda r : r.Id == room)
        for id in near :
            r.Near.append(Find(self.Rooms, lambda r : r.Id == id))

    #Prints out the current setup of allocations in the CSP 
    def ListAllocations(self) :
        output = ""
        for room in self.Rooms :
            print(room.Id, ", WorkPlaces: ", room.WorkPlaces, ", VisitorPlaces: ", room.VisitorPlaces, "\tNear: ", sep="", end="")
            for r in room.Near :
                print(r.Id, ", ", sep="", end="")
            print()
            totVisitors = 0
            for person in room.Occupants :
                print("  ", person.Id, ", Profession: ", person.Profession, ", Garlic lover: ", person.GarlicLover, sep ="", end ="")
                print(", Max num visitors: ", person.MaxVisitors, sep="")
                totVisitors += person.MaxVisitors
            print("  Total number of visitors: ", totVisitors, "\n", sep="")
        print("Number of room fitting tests: ", self.RoomFittingTests, sep="")

    #Allocate persons into room using either a smart or an naive search method
    def Allocate(self, runNaive = True) :
        for room in self.Rooms :
            room.Occupants.clear()
        for person in self.Persons :
            person.AssignedToRoom = False;
        self.RoomFittingTests = 0;
        if runNaive :
            return self.AllocateNaive()
        else :
            return self.AllocateSmart()

    #Allocates persons into rooms by simply assigning people to rooms and backtracking when
    #something is inconsistent with the constraints
    def AllocateNaive(self) :
        i = 0;
        #Get the first person who is not assigned to a room
        while self.Persons[i].AssignedToRoom :
            i += 1
            #if everyone is assigned to a room
            if i >= len(self.Persons) :
                return True
        for room in self.Rooms :
            room.Occupants.append(self.Persons[i])
            self.Persons[i].AssignedToRoom = True
            #if the assignment directly breaks a constraint, undo it
            if not self.CheckConstraints(self.Persons[i], room) :
                room.Occupants.remove(self.Persons[i])
                self.Persons[i].AssignedToRoom = False
            #recursivly do more assignments
            elif self.AllocateNaive() :
                return True
            #if the subsequent assignment failed for all options, undo the current assignment
            else :
                room.Occupants.remove(self.Persons[i])
                self.Persons[i].AssignedToRoom = False
        #if no valid value
        return False

    #Allocates persons into rooms using forwardchecking and testwise allocation
    def AllocateSmart(self) :
        self.UpdatePossibleAlloc()
        person = self.GetLowestPossible()
        #if there are no unassigned persons
        if person == None :
            return True
        #for all possible values, choose the least restrictive
        for t in self.TestAllocation(person) :
            t[1].Occupants.append(person)
            person.AssignedToRoom = True            
            #if the assignment directly breaks a constraint, undo it
            if not self.CheckConstraints(person, t[1]) :
                t[1].Occupants.remove(person)
                person.AssignedToRoom = False
            #recursivly do more assignments
            elif self.AllocateSmart() :
                return True
            #if the subsequent assignment failed for all options, undo the current assignment
            else :                
                t[1].Occupants.remove(person)
                person.AssignedToRoom = False
        #if no valid value
        return False

    #Gets the person that has the lowest amount of possible assignments and who is involved in the most constraints
    def GetLowestPossible(self) :
        lowestPossible = len(self.Rooms) + 1
        lowestPossiblePerson = None
        for person in self.Persons :
            if not person.AssignedToRoom and len(person.PossibleRooms) < lowestPossible :
                lowestPossiblePerson = person
                lowestPossible = len(person.PossibleRooms)
            #if they're equal, tiebreak with that secretaries and IT-support should be prioritized
            elif not person.AssignedToRoom and len(person.PossibleRooms) == lowestPossible :
                if person.Profession == Professions.ItSupport or person.Profession == Professions.Secretary :
                    lowestPossiblePerson = person;
                    lowestPossible = len(person.PossibleRooms);
        return lowestPossiblePerson

    #Updates everyones possible assignments (domains)
    def UpdatePossibleAlloc(self):
        agenda = []
        bosses = []
        bossesNotChecked = self.FillAgendaAndBosses(agenda, bosses)
        while len(agenda) != 0 :
            person = agenda.pop(0)
            if not person.AssignedToRoom :
                if person.Profession == Professions.ItSupport or person.Profession == Professions.Secretary :
                    #Make sure all bosses have been assigned to rooms before checking IT and Secretaries
                    if bossesNotChecked == 0 :
                        self.SecITPossibleAlloc(person, bosses)
                    else :
                        agenda.append(person)
                elif person.Profession == Professions.Boss :
                    self.BossPossibleAlloc(person)
                    bossesNotChecked -= 1
                else :
                    self.WorkerPossibleAlloc(person)
            elif person.Profession == Professions.Boss :
                    bossesNotChecked -= 1

    #Get possible allocations for IT-support and Secretaries, i.e. all rooms near to rooms that bosses can sit in
    def SecITPossibleAlloc(self, person, bosses) :
        person.PossibleRooms.clear()
        for boss in bosses :
            for room in boss.PossibleRooms :
                for near in room.Near :
                    if not near in person.PossibleRooms :
                        sumVisitors = 0
                        for p in near.Occupants :
                            sumVisitors += p.MaxVisitors
                        if len(near.Occupants) < near.WorkPlaces and near.VisitorPlaces >= sumVisitors + person.MaxVisitors :
                            person.PossibleRooms.append(near)

    #Get possible allocation for workers, i.e. all rooms that have enough room for them and for their visitors and do not have a boss in them
    def WorkerPossibleAlloc(self, person) :
        person.PossibleRooms.clear();
        for room in self.Rooms :
            sumVisitors = 0
            noBossInRoom = True
            for p in room.Occupants :
                sumVisitors += p.MaxVisitors
                if p.Profession == Professions.Boss :
                    noBossInRoom = False;
            if noBossInRoom and len(room.Occupants) < room.WorkPlaces and room.VisitorPlaces >= sumVisitors + person.MaxVisitors :
                person.PossibleRooms.append(room);

    #Get possible allocations for bosses, i.e. all rooms that are empty and that have room for their visitors
    def BossPossibleAlloc(self, person) :
        person.PossibleRooms.clear();
        for room in self.Rooms :
            if len(room.Occupants) == 0 and room.VisitorPlaces >= 5:
                person.PossibleRooms.append(room);

    #Fills the agenda with all the persons and also adds all bosses to the bosses list
    #returns the amount of bosses that are found
    def FillAgendaAndBosses(self, agenda, bosses) :
        bossesNotChecked = 0;
        for person in self.Persons :
            agenda.append(person)
            if person.Profession == Professions.Boss :
                bossesNotChecked += 1
                bosses.append(person)
        return bossesNotChecked

    #Performs testwise allocation keeping track of how many possible allocations are available
    #for everybody else after a specific allocation and returns a list sorted after this value
    def TestAllocation(self, person) :
        result = []
        for room in person.PossibleRooms : 
            room.Occupants.append(person)
            person.AssignedToRoom = True;
            self.UpdatePossibleAlloc();
            sumPossible = 0;
            okAssignment = True;
            for p in self.Persons :
                if not p.AssignedToRoom :
                    if len(p.PossibleRooms) == 0 :
                        okAssignment = false
                        break
                    sumPossible += len(p.PossibleRooms);
            if okAssignment :
                result.append((sumPossible, room));
            room.Occupants.remove(person);
            person.AssignedToRoom = False;
        result.sort(key = lambda x : x[0])
        return result

    #Check all constraints
    def CheckConstraints(self, person, room) :
        self.RoomFittingTests += 1
        if not self.CheckRoomCapacity(person, room) :
            return False
        if not self.CheckBossIsAlone(person, room) :
            return False
        if not self.CheckSecretaryNearBoss(person, room) :
            return False
        if not self.CheckItSupportNearBoss(person, room) :
            return False
        if not self.CheckGarlicLovers(person, room) :
            return False
        if not self.CheckVisitorSpace(person, room) :
            return False
        return True

    def CheckRoomCapacity(self, person, room) :
        if (len(room.Occupants) > room.WorkPlaces) :
             return False;
        return True;

    def CheckBossIsAlone(self, person, room) :
        if (person.Profession == Professions.Boss) :
            if (len(room.Occupants) > 1) :
                return False
        else :
            for p in room.Occupants :
                if p.Profession == Professions.Boss :
                    return False;
        return True;

    def CheckSecretaryNearBoss(self, person, room) :
        if person.Profession != Professions.Secretary :
            return True;
        for adjacent in room.Near :
            for p in adjacent.Occupants :
                if p.Profession == Professions.Boss :
                    return True
        return False;

    def CheckItSupportNearBoss(self, person, room) :
        if person.Profession != Professions.ItSupport :
            return True;
        for adjacent in room.Near :
            for p in adjacent.Occupants :
                if p.Profession == Professions.Boss :
                    return True
        return False;

    def CheckGarlicLovers(self, person, room) :
        for p in room.Occupants :
            if person.GarlicLover != p.GarlicLover :
                return False;
        return True;

    def CheckVisitorSpace(self, person, room) :
        numVisitors = 0
        for p in room.Occupants :
            numVisitors += p.MaxVisitors
        if numVisitors > room.VisitorPlaces :
            return False
        return True;